package org.example.myleet.p1743;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

    static class Node {
        int val;
        Node l1;
        Node l2;

        public Node(int val) {
            this.val = val;
        }
    }

    private int idx = 0;

    public int[] restoreArray(int[][] adjacentPairs) {
        idx = 0;
        Map<Integer, Node> valueNodeMap = new HashMap<>();
        int[] pair;
        Node n0;
        Node n1;
        //遍历所有数对，重新构成节点并连接成图
        for (int[] adjacentPair : adjacentPairs) {
            pair = adjacentPair;
            //用哈希表快速找到对应节点
            n0 = valueNodeMap.getOrDefault(pair[0], new Node(pair[0]));
            n1 = valueNodeMap.getOrDefault(pair[1], new Node(pair[1]));
            if (n0.l1 == null) {
                n0.l1 = n1;
            } else {
                n0.l2 = n1;
            }
            if (n1.l1 == null) {
                n1.l1 = n0;
            } else {
                n1.l2 = n0;
            }
            valueNodeMap.put(pair[0], n0);
            valueNodeMap.put(pair[1], n1);
        }
        //寻找其中一个链头
        Node head = null;
        for (Map.Entry<Integer, Node> entry : valueNodeMap.entrySet()) {
            if (entry.getValue().l2 == null) {
                head = entry.getValue();
                break;
            }
        }
        Set<Integer> visited = new HashSet<>(adjacentPairs.length + 1);
        int[] result = new int[adjacentPairs.length + 1];
        visit(head, visited, result);
        return result;
    }

    /**
     * 递归，遍历这个链表，追加结果
     */
    private void visit(Node cur, Set<Integer> visited, int[] result) {
        if (null == cur) {
            return;
        }
        if (visited.contains(cur.val)) {
            return;
        } else {
            result[idx++] = cur.val;
            visited.add(cur.val);
        }
        visit(cur.l1, visited, result);
        visit(cur.l2, visited, result);
    }
}
